class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
      if(head==nullptr||head->next==nullptr) return head;
      ListNode* dHead = new ListNode(0);
       dHead->next = head;
      ListNode* last=head,*r=head->next,*p=dHead;
      while(r!=nullptr){
        if(r->val>=last->val){
          last=last->next;
        }else{
          p=dHead;
          while(p->next->val<=r->val){
            p=p->next;
          }
          last->next=r->next;
          r->next=p->next;
          p->next=r;
        }
        r=last->next;
      }
      return dHead->next;
    }
};
